package 位运算;
import java.util.*;
/**
 * 计算从0到n的每个数字的二进制表示中1的个数
 * 时间复杂度O(n)，空间复杂度O(n)，n为输入数字
 */
public class countBits {
    /**
     * 计算从0到n的每个数字的二进制表示中1的个数
     * 
     * @param n 输入数字
     * @return 包含每个数字二进制表示中1的个数的数组
     */
    public int[] cntBit(int n){
        int[] res = new int[n + 1]; // 用于存储结果的数组
        res[0] = 0; // 0的二进制表示中1的个数为0
        for(int i = 1; i <= n; i++){ // 遍历从1到n的每个数字
            if((i & 1) == 1) res[i] = res[i - 1] + 1; // 如果当前数字是奇数，则1的个数为前一个数字的1的个数加1
            else res[i] = res[i >> 1]; // 如果当前数字是偶数，则1的个数为当前数字右移一位后的1的个数
        }
        return res; // 返回结果数组
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一个整数n
     * 例如：5 表示输入数字
     * 输出格式：包含每个数字二进制表示中1的个数的数组
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取输入数字
        countBits cb = new countBits(); // 创建实例
        int[] res = cb.cntBit(n); // 计算每个数字的二进制表示中1的个数
        System.out.println(Arrays.toString(res)); // 输出结果数组
        sc.close(); // 关闭输入流
    }
}
